package com.mango.algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序-优化版本
 * 空间复杂度：O(1)
 * 时间复杂度：O(n2)
 * 1. 先找到最小的数做哨兵，放到最左边
 * 2. 从第3个数开始，发现左边的数大于右边的，就右移动，最后把原来的数赋值给适合的下标
 * 例子：13,7,4,6,9,24,12
 * 1) 4,13,7,6,9,12,24 # 找到最小的数放左边做哨兵
 *
 * 2.1) 4 13 _ 6 9 12 24 # value = 7
 * 2.2) 4 _ 13 6 9 12 24 # 13向后移动一位
 * 2.3）4 7 13 6 9 12 24 # 7插入到对应位置
 *
 * old:[13, 7, 4, 6, 9, 24, 12]
 * 1)[4, 13, 7, 6, 9, 12, 24]
 * 2)[4, 7, 13, 6, 9, 12, 24]
 * 3)[4, 6, 7, 13, 9, 12, 24]
 * 4)[4, 6, 7, 9, 13, 12, 24]
 * 5)[4, 6, 7, 9, 12, 13, 24]
 * 6)[4, 6, 7, 9, 12, 13, 24]
 * result:[4, 6, 7, 9, 12, 13, 24]
 */
public class InsertXSort {
    public static void main(String[] args) {
        int[] nums = {13,7,4,6,9,24,12};
        System.out.println("old:"+Arrays.toString(nums));
        System.out.println("result:"+Arrays.toString(sort(nums)));
    }
    // 插入排序
    public static int[] sort(int[] nums){
        int swap = 0;
        // 找到最小的数字做为哨兵
        for(int i=nums.length-1;i>0;i--){
            if(nums[i] < nums[i-1]){
                swap(nums,i,i-1);
                swap ++;
            }
        }
        if(swap == 0) return nums;
        System.out.println("1)"+Arrays.toString(nums));
        // 从第二位数字开始对比，如果后面数字比前面数字大，将大的数字统一往后面移动，最后将原来数组插入到对应下标
        for(int i=2;i<nums.length;i++){
            int j=i;
            int value = nums[i];
            while(value < nums[j-1]){
                nums[j] = nums[j-1];
                j--;
            }
            nums[j] = value;
            System.out.println(i+")"+Arrays.toString(nums));
        }
        return nums;
    }
    // 交换数组下标
    public static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
